package me.algo;

import me.algo.coll2.LinkedLst;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.TreeSet;
import java.util.stream.Collectors;

/**
 * @author guozheng
 * @date 2024/3/28
 */
public class M3 {
    public static void main(String[] args) {
        var nums = new int[]{};
        List<String> strings = summaryRanges(nums);
        System.out.println(strings);


        int[][] range = new int[][]{{1,4},{4,5}};
        int[][] merge = merge(range);

    }

    public static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,
                Comparator.comparingInt((int[] o) -> o[0]).thenComparing((o1, o2) -> o2[1] - o1[1]));
        ArrayList<int[]> list = new ArrayList<>();
        for (int[] interval : intervals) {
            list.add(interval);
        }
        int last = list.size();
        int current = last;
        do {
            for (int i = 1; i < list.size(); i++) {
                int[] ints1 = list.get(i - 1);
                int[] ints2 = list.get(i);
                if (canMerge(ints1, ints2)) {
                    int[] mgd = mergeTwo(ints1, ints2);
                    list.set(i - 1,mgd);
                    list.remove(i);
                    i--;
                }
            }
            last = current;
            current = list.size();
        } while (last != current);
//        for (int i = 0; i < intervals.length; i++) {
//            int[] ra = intervals[i];
//            if (ints.isEmpty()) {
//                ints.addLast(ra);
//            } else {
//                int size = ints.size();
//                while (size > 0) {
//                    int[] exists = ints.removeFirst();
//                    if (canMerge(exists, ra)) {
//                        int[] mgd = mergeTwo(exists, ra);
//                        ints.addLast(mgd);
//                    } else {
//                        ints.addLast(exists);
//                        ints.addLast(ra);
//                    }
//                    size--;
//                }
//            }
//        }
        List<int[]> collect = list.stream().distinct().collect(Collectors.toList());
        int[][] result = new int[collect.size()][2];
        collect.toArray(result);
        return result;
    }

    static boolean canMerge(int[] a, int[] b) {
        int aRight = a[1];
        int bLeft = b[0];
        int aLeft = a[0];
        int bRight = b[1];
        // |--a--|
        //        |---b---|

        // |--a--|
        //      |---b---|
        //              |--a--|
        //      |---b---|
        if (aRight >= bLeft & aLeft <= bRight) {
            return true;
        }
        return false;
    }

    static int[] mergeTwo(int[] a, int[] b) {
        if (!canMerge(a, b)) {
            throw new RuntimeException();
        }
        int aRight = a[1];
        int bLeft = b[0];
        int aLeft = a[0];
        int bRight = b[1];
        // a包含b
        // |--a----------|
        //      |---b---|
        if (aRight >= bRight && aLeft <= bLeft) {
            return a;
        }
        // b包含a
        //   |---a----|
        //  |-------b---|
        if (aRight <= bRight && aLeft >= bLeft) {
            return b;
        }
        //a 在b的左侧
        // b包含a
        //   |---a----|
        //         |-------b---|
        //   |---a-------------|
        //         |-------b----|
        //   |---a-|
        //         |-------b----|
        if (aLeft < bLeft && aRight >= bLeft) {
            return new int[]{aLeft, bRight};
        }
        //a 在b的右侧
        // b包含a
        //                   |---a----|
        //         |-------b---|
        //         |---a-------------|
        //         |-------b----|
        //                 |---a-|
        //         |-------b----|
        if (aLeft <= bRight && aLeft > bLeft) {
            return new int[]{bLeft, aRight};
        }
        throw new RuntimeException();
    }




    public static List<String> summaryRanges(int[] nums) {
        if (Objects.isNull(nums) || nums.length == 0) {
            return new ArrayList<>();
        }
        List<String> res = new ArrayList<>();
        LinkedList<Integer> stk = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            if (stk.isEmpty()) {
                stk.addLast(nums[i]);
            } else {
                Integer last = stk.peekLast();
                int val = nums[i];
                if ((last + 1) == val) {
                    stk.addLast(val);
                } else {
                    if (stk.size() == 1) {
                        res.add(Objects.toString(stk.peekFirst()));
                    } else {
                        String v = String.join("->", Objects.toString(stk.peekFirst()), Objects.toString(stk.peekLast()));
                        res.add(v);
                    }
                    stk.clear();
                    stk.addLast(val);
                }
            }
        }
        if (stk.size() == 1) {
            res.add(Objects.toString(stk.peekFirst()));
        } else {
            String v = String.join("->", Objects.toString(stk.peekFirst()), Objects.toString(stk.peekLast()));
            res.add(v);
        }
        return res;
    }
}
